package com.example.question.tree.tree3;

import com.example.question.tree.tree1.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Date 2023-07-15
 * @Author Jonathan
 */
public class Code13_538 {
    public static void main(String[] args) {

    }

    // 1 2 3 4 5 6 7 8
    //  先右子树 再根节点 最后是 左子树

    public TreeNode convertBST(TreeNode root) {
        inOrder(root);
        return root;
    }

    int sum = 0;

    private void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.right);
        int tmp = node.val;
        node.val = node.val + sum;
        sum += tmp;
        inOrder(node.left);
    }


    public TreeNode convertBST1(TreeNode root) {
        dfs(root);
        int sum = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            valSumMap.put(list.get(i), sum);
            sum += list.get(i);
        }
        updateVal(root);
        return root;
    }

    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> valSumMap = new HashMap<>();

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        list.add(node.val);
        dfs(node.right);
    }

    private void updateVal(TreeNode node) {
        if (node == null) return;
        updateVal(node.left);
        updateVal(node.right);
        node.val = node.val + valSumMap.get(node.val);
    }


}
